// map.hpp
// Map, an unordered key->value collection.
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef R_MAP_HPP
#define R_MAP_HPP

#include "util/standard.hpp"

namespace Ripe {
  enum BucketType{
    BucketFull,  // This bucket contains a key->value pair.
    BucketEmpty, // This bucket is empty.
    BucketLazy   // This bucket was lazily removed.
  };

  template <class K, class V>
  class Bucket{
    public:
      BucketType type;
      K key;
      V value;
  };

  // Default number of elements in a map:
  #ifndef R_MAP_DEFAULT_SIZE
  #define R_MAP_DEFAULT_SIZE 2
  #endif
  
  template <class K, class V>
  class Map;  
  
  // Iterator that can be used to go through the elements of the map. Do not
  // modify the map while iterating.
  template <class K, class V>
  class MapIterator {
    public:
      MapIterator(Map<K,V>* m);
      
      bool get(K* k, V* v);
      
    private:
      Map<K,V>* map;
      
      uint32_t i;
  };

  template <class K, class V>
  class Map {
    public:
      // Construct a map preallocated with space for n items.
      Map(uint32_t n = R_MAP_DEFAULT_SIZE);

      // Number of key->value pairs in the map.
      uint32_t size;

      // Lookup the given key.
      // If it is found, return true. Place the value into the location pointed
      // to by value.
      //
      // If key is not found, location at value is not changed.
      bool get(K key, V* value);

      // Set a key->value pair.
      bool set(K key, V value);

      // Output a graphical representation of the map.
      void  print();

      friend class MapIterator<K,V>;
    private:
      // Number of buckets allocated.
      uint32_t alloc_size;

      Bucket<K,V>* data;

      // Internal: Set a key->value pair in the given size-many buckets.
      bool set2(Bucket<K,V>* buckets, uint32_t size, K key, V value);
  };

  // We use another set of templates in order to template-specialize the
  // functions map_hash_key and map_equal_key.

  // Hash the key.
  template <class T>
  static inline uint32_t map_hash_key(T key);

  // Decide if two keys are equal.
  template <class T>
  static inline bool map_equal_key(T k1, T k2);

  // char* specialization
  template <>
  static inline uint32_t map_hash_key(char* key);
  template <>
  static inline bool map_equal_key(char* k1, char* k2);
}

#include "map.cpp"

#endif // R_MAP_HPP
